package algorithm.math;

/**
 * leetcode : https://leetcode.com/problems/divide-two-integers/description/
 * Difficulty : Medium
 *
 * 两个有符号数相除，不允许使用乘法，除法，和取模运算。（有的解法使用long，但原则上来说也不应该使用long）
 * 难点在于边界值处理
 *
 * 最直观的方法是不断的减去被除数，但是这样的时间复杂度会是O(N)
 * 有个解法是用位运算
 * 解法参考：https://leetcode.com/problems/divide-two-integers/discuss/142849/C++JavaPython-Should-Not-Use-"long"-Int
 *
 * @Author Antony
 * @Since 2018/7/11 11:41
 */
public class DivideTwoIntegers {

    public static void main(String[] args) {
        int a = Integer.MIN_VALUE;
        int b = -1;
        System.out.println(divide(a,b));
    }


    /**
     * (beats 98.17% - 22ms)
     * 位运算
     */
    public static int divide(int dividend, int divisor) {
        if(dividend == 1 << 31 && divisor == -1) return  (1<<31)-1;
        int a = Math.abs(dividend);
        int b = Math.abs(divisor);
        int res = 0;
        for(int x=31; x>=0; x--){
            if((a >>> x) -b >= 0){
                res += 1<<x;
                a -= b<<x;
            }
        }
        return (dividend>0) == (divisor>0) ? res : -res;
    }
}
